1. Field of the Invention
This invention relates in general to the field of instruction execution in computers, and more particularly to an apparatus and method for predicting the outcome of branch instructions in a pipeline microprocessor.
2. Description of the Related Art
An application program for execution on a microprocessor consists of a structured series of macro instructions that are stored in sequential locations in memory. A current instruction pointer within the microprocessor points to the address of the instruction currently being executed and a next instruction pointer within the microprocessor points to the address of the next instruction for execution. During each clock cycle, the length of the current instruction is added to the contents of the current instruction pointer to form a pointer to a next sequential instruction in memory. The pointer to the next sequential instruction is provided to logic that updates the next instruction pointer. If the logic determines that the next sequential instruction is indeed required for execution, then the next instruction pointer is updated with the pointer to the next sequential instruction in memory. Thus, macro instructions are fetched from memory in sequence for execution by the microprocessor.
Obviously, because a microprocessor is designed to execute instructions from memory in the sequence that they are stored, it follows that a program configured to execute macro instructions sequentially from memory is one that will run efficiently on the microprocessor. For this reason, most application programs are designed to minimize the number of instances where macro instructions are executed out of sequence. These out-of-sequence instances are known as jumps, or branches.
A program branch presents a problem because most conventional microprocessors do not simply execute one instruction at a time. Rather, a present day microprocessor consists of a number of pipeline stages, each stage performing a specific function. Instructions, inputs, and results from one stage to the next are passed in synchronization with a pipeline clock. Hence, several instructions may be executing in different stages of the microprocessor pipeline within the same clock cycle. Consequently, when logic within a given stage determines that a program branch is to occur, then instructions in previous stages of the pipeline must be cast out so that control of the microprocessor can be transferred to the instruction directed by the branch, or the branch target instruction. This casting out of instructions in previous pipeline stages is known as flushing the pipeline.
A conditional branch is a branch. that may or may not occur, depending upon an evaluation of some specified condition. And this evaluation is typically performed in later stages of the microprocessor pipeline. To preclude wasting many clock cycles associated with flushing and refilling the pipeline, present day microprocessors also provide logic in an early pipeline stage that predicts whether a conditional branch will occur or not, that is, whether it will be taken or not taken. If it is predicted that a conditional branch will be taken, then only those instructions prior to the early pipeline stage must be flushed, including those in the instruction buffer. Even so, this is a drastic improvement; correctly predicted branches are executed in roughly two clock cycles. But an incorrect prediction takes many more cycles to execute than if no branch prediction mechanism had been provided in the first place. The accuracy of branch predictions in a pipeline processor significantly impact the processor""s performance, for better or worse.
Present day branch prediction mechanisms primarily predict the outcome of a given conditional branch instruction in an application program based upon outcomes obtained when the conditional branch instruction was previously executed within the same instance of the application program. This historical branch prediction, or dynamic branch prediction, is effective because conditional branch instructions tend to exhibit repetitive outcome patterns.
In a conventional microprocessor, the historical outcome data is stored in a single branch history table that is accessed using the address of a conditional branch instruction-a unique identifier for the instruction. A corresponding entry in the branch history table contains the historical outcome data associated with the conditional branch instruction. A dynamic prediction of the outcome of the conditional branch instruction is made based upon the contents of the corresponding entry in the branch history table.
Yet, because most present day microprocessors have address ranges on the order of gigabytes, it is not practical for a branch history table to be as large as the microprocessor""s address range. Because of this, smaller branch history tables are provided, on the order of kilobytes, and only the low-order bits of a conditional branch instruction""s address are used as an index into the table. But this presents another problem: because low-order address bits are used to index the branch history table, two or more conditional branch instructions can index the same entry. This is known as aliasing. As such, the outcome of a more recently executed conditional branch instruction will influence the historical outcome record of a formerly executed conditional branch instruction that is aliased to the same table entry. If the former conditional branch instruction is encountered again, its historical outcome information is biased, for better or for worse, toward the outcome of the more recently executed conditional branch instruction.
The present inventors have observed that the outcomes of conditional branch instructions, when observed on pipeline microprocessor executing today""s predominant desktop computer application programs exhibit a bias toward one outcome or the other as a function of static indicators such as the type of conditional test performed, regardless of historical outcome data associated with the instructions. Some conditional branch instructions indeed exhibit a very strong bias toward an outcome, virtually independent of execution history in the application program. Thus, execution of an application program is negatively impacted when it has a significant number of conditional branch instructions having conflicting outcome biases that are aliased to the same historical outcome records: predictions for instructions biased toward being taken are negatively influenced by instructions that are biased toward being not taken that are aliased to the same historical outcome record, and vice versa.
Thus, the accuracy of branch predictions is degraded on the whole in a microprocessor that allows the outcomes of conditional branch instructions exhibiting a certain outcome bias to impact the historical outcome data for conditional branch instructions that exhibit a conflicting outcome bias.
Therefore, what is needed is an apparatus for predicting the outcomes of branch instructions that is more accurate than has heretofore been provided.
In addition, what is needed is a branch prediction mechanism in a microprocessor that separately maintains historical outcome records for conditional branch instructions as categorized by outcome bias.
Furthermore, what is needed is an apparatus in a microprocessor for predicting branches that precludes outcomes associated with conditional branch instructions having a certain outcome bias from influencing branch predictions for other branch instructions that exhibit a bias toward a different outcome.
Moreover, what is needed is a method for separating historical outcome data for conditional branch instructions that improves the accuracy of their associated branch predictions.
To address the above-detailed deficiencies, it is an object of the present invention to provide a branch prediction apparatus that provides accurate branch predictions by segregating outcome records for conditional branch instructions according to their observed outcome bias.
Accordingly, in the attainment of the aforementioned object, it is a feature of the present invention to provide an apparatus in a microprocessor for performing branch prediction. The apparatus includes a bias indicator and a dynamic branch predictor. The bias indicator receives a branch instruction from an instruction buffer and provides an output indicating a particular outcome bias category for the branch instruction. The bias indicator provides the output as a function of a branch type and a displacement, where the branch type and the displacement are prescribed by the branch instruction The dynamic branch predictor is coupled to the bias indicator. The dynamic branch predictor receives the output and predicts an outcome for the branch instruction based upon contents of an entry in a particular branch history table, where the particular branch history table corresponds to the particular outcome bias category, and where the dynamic branch predictor maintains a plurality of branch history tables, each of the plurality of branch history tables corresponding to an outcome bias category, and where the outcome bias category is selected from a plurality of outcome bias categories, and where the plurality of outcome bias categories comprises a taken category and a not taken category.
An advantage of the present invention is that more accurate branch predictions are generated in a microprocessor than have heretofore been obtained.
Another object of the present invention is to an apparatus in a microprocessor to predict branch outcomes for conditional branch instructions exhibiting a particular outcome bias based upon historical outcome data for conditional branch instructions that exhibit the same particular outcome bias.
In another aspect, it is a feature of the present invention to provide a branch prediction mechanism for performing branch predictions in a microprocessor. The branch prediction mechanism has a bias indicator, a dynamic branch predictor, and branch history update logic. The bias indicator receives a branch instruction from an instruction buffer and provides an output indicating a particular outcome bias category for the branch instruction, where the bias indicator provides the output as a function of a branch type and a displacement, the branch type and the displacement being prescribed by the branch instruction. The dynamic branch predictor is coupled to the bias indicator. The dynamic branch predictor receives the output and predicts an outcome for the branch instruction based upon contents of an entry in a particular branch history table, where the particular branch history table corresponds to the particular outcome bias category. The branch history update logic is coupled to the split dynamic branch predictor. The branch history update logic updates the entry following resolution of the branch instruction. Another advantage of the present invention is that execution speed of an application program is improved because unnecessary pipeline flushes due to incorrect branch predictions are reduced.
A further object of the invention is to provide an apparatus in a microprocessor for predicting branches that precludes outcomes associated with conditional branch instructions having a certain outcome bias from influencing branch predictions for other branch instructions that exhibit a bias toward a different outcome.
In a further aspect, it is a feature of the present invention to provide a branch prediction apparatus. The branch prediction apparatus includes a bias indicator and a dynamic branch predictor. The bias indicator provides an output indicating a particular outcome bias category for a particular branch instruction, where the bias indicator provides the output as a function of a branch type and a displacement, the branch type and the displacement being prescribed by the particular branch instruction. The dynamic branch predictor is coupled to the bias indicator and directs a next instruction pointer to indicate a next sequential instruction address or a branch target address. The dynamic branch predictor has a plurality of branch history tables. Each of the plurality of branch history tables receives an instruction pointer and maintains corresponding branch outcome data, where a particular branch history table contains particular branch outcome data associated with the particular outcome bias category.
A further advantage of the present invention is that application programs having significant numbers of program branches execute more efficiently. Yet another object of the present invention is to provide a method for separating historical outcome data for conditional branch instructions that improves the accuracy of their associated branch predictions.
In yet another aspect, it is a feature of the present invention to provide a method for performing branch prediction in a microprocessor. The method includes maintaining a plurality of branch history tables containing historical outcome records for branch instructions, each of the plurality of branch history tables being indexed by an instruction pointer; employing a specific outcome bias category to identify a specific branch history table for a specific branch instruction; and predicting an outcome of the specific branch instruction based upon contents of a specific historical outcome record corresponding to the specific outcome bias category. The employing includes categorizing branch instructions according to observed outcome bias; and during translation of a branch instruction, providing a corresponding outcome bias category to a branch predictor, where a displacement prescribed by the branch instruction is used by the providing to determine the corresponding outcome bias category. The predicting includes: evaluating contents of the specific historical outcome record to determine if it is more likely that a branch will be taken or not taken; and generating a predicted outcome signal for the specific branch instruction in accordance with the evaluating.
Yet another advantage of the present invention is that a method is provided to reduce the confusion created in a branch history table by intermixing results of conditional branch instructions having a given outcome bias with results of conditional branch instructions having a conflicting outcome bias.